package com.kiven.quicksort;

public class Array4Sort
	{
	    private long[]    longArray;            // 待排序的数组

	    private int        nElems;                // 数组内元素个数,也就是下标值

	    private int        maxSize;            // 数组大小

	    private int[]    intervalSequence;    // 增量数组序列


	    public Array4Sort( int max )
	    {
	        maxSize = max;
	        longArray = new long[maxSize];
	        nElems = 0;
	    }
	    
	    /**
	     * 插入一个元素到数组中，数组里的数据长度增一
	     * @param value
	     */
	    public void insert( long value )
	    {
	        longArray[nElems] = value;
	        nElems++ ;
	    }

	    /**
	     * 通过随机数初始化数组
	     */
	    public void initRandom()
	    {
	        nElems = 0;
	        for ( int i = 0; i < maxSize; i++ )
	        {
	            long n = (long) ( java.lang.Math.random( ) * maxSize * 10 );
	            insert( n );
	        }
	        nElems = maxSize;//插入了maxSize个元素

	    }
	    
	    /**
	     * 打印数组数据
	     *
	     */
	    public void displayArray()
	    {
	        System.out.print( "\t" );
	        for ( int i = 0; i < nElems; i++ )
	        {
	            System.out.print( longArray[i] + " " );
	        }
	        System.out.println( "" );
	    }
	    


	    /**
	     * 快速排序
	     *
	     * 基本思想
	     * 　设当前待排序的无序区为R[low..high]，利用分治法可将快速排序的基本思想描述为：
	     * ①分解：
	     * 在R[low..high]中任选一个记录作为基准(Pivot)，
	     * 以此基准将当前无序区划分为左、右两个较小的子区间R[low..pivotpos-1)和R[pivotpos+1..high]，
	     * 并使左边子区间中所有记录的关键字均小于等于基准记录(不妨记为pivot)的关键字pivot.key，
	     * 右边的子区间中所有记录的关键字均大于等于pivot.key，
	     * 而基准记录pivot则位于正确的位置(pivotpos)上，它无须参加后续的排序。
	     * 注意：
	     * 划分的关键是要求出基准记录所在的位置pivotpos。
	     * 划分的结果可以简单地表示为(注意pivot=R[pivotpos])：
	     * R[low..pivotpos-1].keys≤R[pivotpos].key≤R[pivotpos+1..high].keys
	     * 其中low≤pivotpos≤high。
	     * ②求解：
	     * 　通过递归调用快速排序对左、右子区间R[low..pivotpos-1]和R[pivotpos+1..high]快速排序。
	     */
	    public void recursionQuickSort( int left, int right )
	    {
	        if ( left >= right )
	        {
	            return;
	        } else
	        {
	            int pivotpos = partition(left, right);
//	            displayArray();

	            recursionQuickSort(left, pivotpos-1); // sort left side

	            recursionQuickSort(pivotpos+1, right); // sort right side

	        }
	    }
	    
	    /**
	     *
	     * 以 longArray[left] 为pivot value将数组longArray中大于pivot value的值放到右边，小于的放到左边，
	     * 中间就是pivot value，并返回pivot value所在的index
	     *
	     * @param left 左边index
	     * @param right 右边index
	     * @return 返回pivot value所在的index，称之为pivotpos
	     */
	    public int partition( int left, int right) {
	        long pivotValue = longArray[left];
	        while ( left<right )
	        {
	            //从右向左扫描，查找第1个元素值小于pivotValue的元素

	            while ( left < right && pivotValue <= longArray[right] )
	            {
	                 right--;
	            }
	            if ( left<right )//表明找到一个元素值小于pivotValue的元素longArray[right]

	            {
	                longArray[left] = longArray[right];
	                left++;//左边游标向右移一格

	            }
	            
	            //从左向右扫描，查找第1个元素值大于pivotValue的元素longArray[left]

	            while ( left < right && pivotValue > longArray[left] )
	            {
	                left++;
	            }
	            if ( left<right )//表明找到一个元素值大于pivotValue的元素longArray[left]

	            {
	                longArray[right] = longArray[left];
	                right--;//右左边游标向左移一格

	            }
	        }
	        
	        longArray[left] = pivotValue;
	        return left;
	    }
	    

	    public int getNElems()
	    {
	        return nElems;
	    }


	    public long[] getLongArray()
	    {
	        return longArray;
	    }
	    
	}


